package code;
import java.util.Arrays;


//零钱兑换:https://leetcode.cn/problems/coin-change/

//转移方程推导见完全背包的转移方程推导过程
public class CoinChange {
	//1.dp[i][j]: 从前i个元素中选，金额恰好为j，所需的最小硬币数
    //2.状态转移方程：
    //  dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)
    //3.初始化: dp[0][0]=0
    //   i=0&&j!=0  => max     max表示无法拼成
    //4.返回值： -1或dp[n][amount]
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;
        long[][] dp=new long[n+1][amount+1];
        for(int i=0;i<=n;i++){
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j]=dp[i-1][j];
                if(j-coins[i-1]>=0){
                    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[n][amount]>=Integer.MAX_VALUE?-1:(int)dp[n][amount];
    }
}
